package JZ_Offer.dataStructure.tree;

/**
 * 二叉搜索树的后序遍历序列
 *
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
 * 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
 *
 * @Author piper
 * @Date 2019/12/20 1:52 下午
 */
public class JZ33_二叉搜索树的后序遍历序列 {

    private static boolean VerifySquenceOfBST(int[] sequence) {
        return helpVerify(sequence, 0, sequence.length - 1);
    }

    private static boolean helpVerify(int[] sequence, int start, int root) {
        if (start >= root) return true;
        int rootValue = sequence[root];
        int mid;
        //找到左右子数的分界点
        for (mid = start; mid < root; mid++) {
            if (sequence[mid] > rootValue) {
                break;
            }
        }
        //在右子树中判断是否含有小于root的值，如果有返回false
        for (int i = mid; i < root; i++) {
            if (sequence[i] < rootValue) {
                return false;
            }
        }
        //递归判断左右子树是否符合规则
        return helpVerify(sequence, start, mid - 1) && helpVerify(sequence, mid, root - 1);
    }

    public static void main(String[] args) {
        int[] sequence = {1, 2, 3, 4, 5};
        System.out.println(VerifySquenceOfBST(sequence));
    }
}
